package leetcode.N1_N100;

public class N33 {

    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {4,5,6,7,8,0,1,2};
        System.out.println(s.search(nums, 0));
    }
}

class Solution {

    public int search(int[] nums, int target) {
        int length = nums.length;
        if (length == 0) {
            return -1;
        }
        return doSearch(nums, 0, length - 1, target);
    }

    private int doSearch(int[] nums, int head, int tail, int target) {
        int headValue = nums[head];
        if (headValue == target) {
            return head;
        }
        if (head >= tail) {
            return -1;
        }
        boolean isOrderly = headValue < target;
        int mid = head + (tail - head >> 1);
        int midValue = nums[mid];

        if (target == midValue) {
            return mid;
        }
        if (target < midValue) {
            if (midValue > headValue && !isOrderly) {
                return doSearch(nums, mid + 1, tail, target);
            }
            return doSearch(nums, head + 1, mid - 1, target);
        }

        // 执行到这里有个隐含条件 midValue > target
        if (midValue < headValue && isOrderly) {
            return doSearch(nums, head + 1, mid - 1, target);
        }
        return doSearch(nums, mid + 1, tail, target);
    }
}
